package leetcode.Queue;

import leetcode.BinaryTree.TreeNode;

import java.util.*;

public class NumIslands {

    /**
     * 岛屿的个数
     * <p>
     * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
     * 一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
     * 你可以假设网格的四个边均被水包围。
     * <p>
     * <p>
     * 输入:
     * 11110
     * 11010
     * 11000
     * 00000
     * 输出: 1
     *
     * @param root
     * @return
     */
//    public static int numIslands(char[][] grid) {
//
//
//
//        if(grid==null|| grid.length==0||grid[0].length==0){
//            return 0;
//        }
//
//        int result = 0;
//        int weigh = grid.length;
//        int hight = grid[0].length;
//
//        Queue<Integer> queue = new ArrayDeque<>();
//        HashSet<Integer> set = new HashSet<>();
//
//        int start1 = 0;
//        int start2 = 0;
//        queue.add((grid[start1][start2]+'0'));
//        set.add(start1 * weigh + start2);
//
//        while (!queue.isEmpty()) {
//
//            int n = queue.poll();
//            start1 = n/weigh;
//            start2 = n%weigh;
//
//            if(start1+1<weigh) {
//                if(grid[start1+1][start2]=='1') {
//                }
//            }
//            if(start2+1<hight&&grid[start1][start2+1]=='1') {
//            }
//
//                if (tempNode.left != null) {
//                    queue.add(tempNode.left);
//                }
//                if (tempNode.right != null) {
//                    queue.add(tempNode.right);
//                }
//            }
//            result.add(temp);
//
//        }
//        return result;
//}

    /**
     * 递归的形式查找岛的数量
     * 上下左右的形式寻找，将相邻的陆地都变成海洋
     * @param grid
     * @return
     */
    public static int numIslandsBetter(char[][] grid) {
        int count = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    search(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public static void search(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0')
            return;

        grid[x][y] = '0';

        search(grid, x - 1, y);
        search(grid, x + 1, y);
        search(grid, x, y - 1);
        search(grid, x, y + 1);
    }


    public static void main(String[] args) {
        char[] a1 = {'1', '1', '1', '1', '0'};
        char[] a2 = {'1', '1', '0', '1', '0'};
        char[] a3 = {'1', '1', '0', '0', '0'};
        char[] a4 = {'0', '0', '0', '0', '0'};

        char[][] b = {a1, a2, a3, a4};

        System.out.println(Arrays.asList(numIslandsBetter(b)));

    }
}
